#include "linked_list.h"

void LinkedList::insertAtHead(int val){
	NodePtr newNode = new ListNode(val);
	
	//判断是否为空
	if(head == nullptr){
		head = newNode;
		head->next = nullptr;
		return;
	}
	newNode->next = head;
	head = newNode;
}
void LinkedList::insertAtTail(int val){
	NodePtr newNode = new ListNode(val);
	//链表为空
	if(!head){
		head = newNode;
		return;
	}
	NodePtr current = head;
	//遍历到末尾节点
	while(current->next){
		current = current->next;
	}
	current->next = newNode;
}
void LinkedList::deleteNode(int val){
	//链表为空
	if(head == nullptr)
		return;
	//删除的元素位于头指针指向的节点
	if(head->val == val){
		NodePtr temp = head;
		head = temp->next;
		delete temp;
	}
	
	NodePtr current = head;
	//遍历要删除节点的前一节点
	while(current->next && current->next->val != val){
		//current->next->val确保是前一节点
		current = current->next;
	}
	/*如果链表中不存在值为 val 的节点，那么遍历到链表末尾后 current->next 就是 nullptr 
	，此时不应该执行后面删除节点的操作，否则会引发程序崩溃
	*/
	if(current->next){
		NodePtr temp = current->next;
		current->next = temp->next;
		delete temp;
	}
}

bool LinkedList::search(int val){
	if(head == nullptr)
		return false;
	NodePtr current = head;
	while (current)
	{
		if(current->val == val)
			return true;
		current = current->next;
		
	}
	return false;
}


void LinkedList::printList(){
	if(head == nullptr)
		return;
	NodePtr current = head;
	std::cout<<"List: ";
	while (current)
	{
		std::cout<<current->val<<" ";
		current = current->next;
	}
	std::cout<<std::endl;
}
void LinkedList::printResult(int val){
	bool flag = search(val);
	std::cout<<"search result: "<<flag<<std::endl;
}

NodePtr LinkedList::iterateReverseList(){
	if(head == nullptr)
		return nullptr;
	if(head->next == nullptr)
		return nullptr;
	NodePtr prev = nullptr;  // 用于指向当前节点的前一个节点，初始化为空
	NodePtr current = head; // 指向当前正在处理的节点，初始为头节点
	while(current != nullptr){
		NodePtr nextTemp = current->next; // 先保存当前节点的下一个节点，防止链表断开
		current->next = prev; // 反转指针，让当前节点指向前一个节点
		prev = current; // 更新前一个节点为当前节点
		current = nextTemp;  // 更新当前节点为原来保存的下一个节点
	}
	head = prev;
	return head;  
}

void LinkedList::recursionReverseList(NodePtr pHead){
	if(pHead == nullptr || pHead->next == nullptr){
		head = pHead;
		return;
	}
	
	recursionReverseList(pHead->next);
	NodePtr newHead = pHead->next;
	newHead->next = pHead;
	pHead->next = nullptr;	
}

int LinkedList::getLength(){
	int count = 0;
	if(head == nullptr)
		return 0;
	NodePtr current = head;
	while(current){
		++count;
		current = current->next;
	}
	return count;
}

NodePtr LinkedList::mergeSortedLists(NodePtr list1, NodePtr list2) {
	NodePtr dummy = new ListNode(); // dummy 是一个虚拟头节点，它的作用是简化边界条件的处理
	NodePtr tail = dummy;
	while (list1 && list2) {
		if (list1->val < list2->val) {
			tail->next = list1;
			list1 = list1->next;
		} else {
			tail->next = list2;
			list2 = list2->next;
		}
		tail = tail->next;
	}
	if (list1) {
		tail->next = list1;
	}
	if (list2) {
		tail->next = list2;
	}
	// mergedList 指向新链表的实际头节点，即虚拟头节点的下一个节点。
	NodePtr mergedList = dummy->next;
	delete dummy;
	return mergedList;
}

bool LinkedList::hasCycle(){
	if(head == nullptr)
		return false;
	NodePtr fast = head;
	NodePtr slow = head;
	
	while(fast && slow->next){
		fast = fast->next->next;
		slow = slow->next;
		if(fast == slow)
			return true;
	}
	return false;
}

NodePtr LinkedList::findMiddleNode(){
	if(head == nullptr)
		return nullptr;
	NodePtr fast = head;
	NodePtr slow = head;
	
	while(fast && slow->next){
		slow = slow->next;
		fast = fast->next->next;
		return slow;
	}
}


